home *** CD-ROM | disk | FTP | other *** search
/ Total Network Tools 2002 / NextStepPublishing-TotalNetworkTools2002-Win95.iso / Archive / Misc Servers / Zope.exe / KJSET.PY < prev    next >
Encoding:
Text File  |  1999-07-28  |  6.4 KB  |  255 lines
  1.  
  2. #
  3. # sets implemented using mappings
  4. #  Copyright Aaron Robert Watters, 1994
  5. #
  6. # these only work for "immutable" elements.
  7. # probably not terribly efficient, but easy to implement
  8. # and not as slow as concievably possible.
  9.  
  10. def NewSet(Sequence):
  11.     Result = {}
  12.     for Elt in Sequence:
  13.         Result[Elt] = 1
  14.     return Result
  15.  
  16. def Empty(Set):
  17.     if Set == {}:
  18.        return 1
  19.     else:
  20.        return 0
  21.  
  22. def get_elts(Set):
  23.     return Set.keys()
  24.  
  25. def member(Elt,Set):
  26.     return Set.has_key(Elt)
  27.  
  28. # in place mutators:
  29. # returns if no change otherwise 1
  30.  
  31. def addMember(Elt,Set):
  32.     change = 0
  33.     if not Set.has_key(Elt):
  34.        Set[Elt] = 1
  35.        change = 1
  36.     return change
  37.  
  38. def Augment(Set, OtherSet):
  39.     change = 0
  40.     for Elt in OtherSet.keys():
  41.         if not Set.has_key(Elt):
  42.            Set[Elt] = 1
  43.            change = 1
  44.     return change
  45.  
  46.  
  47. def Mask(Set, OtherSet):
  48.     change = 0
  49.     for Elt in OtherSet.keys():
  50.         if Set.has_key(Elt):
  51.            del Set[Elt]
  52.            change = 1
  53.     return change
  54.  
  55. # side effect free functions
  56.  
  57. def Intersection(Set1, Set2):
  58.     Result = {}
  59.     for Elt in Set1.keys():
  60.         if Set2.has_key(Elt):
  61.            Result[Elt] = 1
  62.     return Result
  63.  
  64. def Difference(Set1, Set2):
  65.     Result = {}
  66.     for Elt in Set1.keys():
  67.         if not Set2.has_key(Elt):
  68.            Result[Elt] = 1
  69.     return Result
  70.  
  71. def Union(Set1,Set2):
  72.     Result = {}
  73.     Augment(Result,Set1)
  74.     Augment(Result,Set2)
  75.     return Result
  76.  
  77. def Subset(Set1,Set2):
  78.     Result = 1
  79.     for Elt in Set1.keys():
  80.         if not Set2.has_key(Elt):
  81.            Result = 0
  82.            return Result # nonlocal
  83.     return Result
  84.  
  85. def Same(Set1,Set2):
  86.     if Subset(Set1,Set2) and Subset(Set2,Set1):
  87.        return 1
  88.     else:
  89.        return 0
  90.  
  91. # directed graphs as Dictionaries of Sets
  92. #   also only works for immutable nodes
  93.  
  94. def NewDG(pairlist):
  95.     Result = {}
  96.     for (source,dest) in pairlist:
  97.         AddArc(Result, source, dest)
  98.     return Result
  99.  
  100. def GetPairs(Graph):
  101.     result = []
  102.     Sources = Graph.keys()
  103.     for S in Sources:
  104.         Dests = get_elts( Graph[S] )
  105.         ThesePairs = [None] * len(Dests)
  106.         for i in range(0,len(Dests)):
  107.             D = Dests[i]
  108.             ThesePairs[i] = (S, D)
  109.         result = result + ThesePairs
  110.     return result
  111.  
  112. def AddArc(Graph, Source, Dest):
  113.     change = 0
  114.     if Graph.has_key(Source):
  115.        Adjacent = Graph[Source]
  116.        if not member(Dest,Adjacent):
  117.           addMember(Dest,Adjacent)
  118.           change = 1
  119.     else:
  120.        Graph[Source] = NewSet( [ Dest ] )
  121.        change = 1
  122.     return change
  123.  
  124. def Neighbors(Graph,Source):
  125.     if Graph.has_key(Source):
  126.        return get_elts(Graph[Source])
  127.     else:
  128.        return []
  129.  
  130. def HasArc(Graph, Source, Dest):
  131.     result = 0
  132.     if Graph.has_key(Source) and member(Dest, Graph[Source]):
  133.        result = 1
  134.     return result
  135.  
  136. def Sources(Graph):
  137.     return Graph.keys()
  138.  
  139. # when G1, G2 and G3 are different graphs this results in
  140. #   G1 = G1 U ( G2 o G3 )
  141. # If G1 is identical to one of G2,G3 the result is somewhat
  142. # nondeterministic (depends on dictionary implementation).
  143. # However, guaranteed that AddComposition(G,G,G) returns
  144. #    G1 U (G1 o G1) <= G <= TC(G1)
  145. # where G1 is G's original value and TC(G1) is its transitive closure
  146. # hence this function can be used for brute force transitive closure
  147. #
  148. def AddComposition(G1, G2, G3):
  149.     change = 0
  150.     for G2Source in Sources(G2):
  151.         for Middle in Neighbors(G2,G2Source):
  152.             for G3Dest in Neighbors(G3, Middle):
  153.                 if not HasArc(G1, G2Source, G3Dest):
  154.                    change = 1
  155.                    AddArc(G1, G2Source, G3Dest)
  156.     return change
  157.  
  158. # in place transitive closure of a graph
  159. def TransClose(Graph):
  160.     change = AddComposition(Graph, Graph, Graph)
  161.     somechange = change
  162.     while change:
  163.        change = AddComposition(Graph, Graph, Graph)
  164.        if not somechange:
  165.           somechange = change
  166.     return somechange
  167.  
  168. ########### SQueue stuff
  169. #
  170. #  A GrabBag should be used to hold objects temporarily for future
  171. #  use.  You can put things in and take them out, with autodelete
  172. #  that's all!
  173.  
  174. # make a new baggy with nothing in it
  175. #   BG[0] is insert cursor BG[1] is delete cursor, others are elts
  176. #
  177. OLD = 1
  178. NEW = 0
  179. START = 2
  180. def NewBG():
  181.     B = [None]*8 #default size
  182.     B[OLD] = START
  183.     B[NEW] = START
  184.     return B
  185.  
  186. def BGempty(B):
  187.     # other ops must maintain this: old == new iff empty
  188.     return B[OLD] == B[NEW]
  189.  
  190. # may return new, larger structure
  191. # must be used with assignment...  B = BGadd(e,B)
  192. def BGadd(elt, B):
  193.     cursor = B[NEW]
  194.     oldlen = len(B)
  195.     # look for an available position
  196.     while B[cursor] != None:
  197.        cursor = cursor+1
  198.        if cursor >= oldlen: cursor = START
  199.        if cursor == B[NEW]: #back to beginning
  200.           break
  201.     # resize if wrapped
  202.     if B[cursor] != None:
  203.        B = B + [None] * oldlen
  204.        cursor = oldlen
  205.        B[OLD] = START
  206.     if B[cursor] != None:
  207.        raise IndexError, "can't insert?"
  208.     # add the elt
  209.     B[cursor] = (elt,)
  210.     B[NEW] = cursor
  211.     # B nonempty so OLD and NEW should differ.
  212.     if B[OLD] == cursor:
  213.        B[NEW] = cursor + 1
  214.        if B[NEW]<=len(B): B[NEW] = START
  215.     return B
  216.  
  217. def BGgetdel(B):
  218.     # find something to delete:
  219.     cursor = B[OLD]
  220.     blen = len(B)
  221.     while B[cursor]==None:
  222.        cursor = cursor+1
  223.        if cursor>=blen: cursor = START
  224.        if cursor == B[OLD]: break # wrapped
  225.     if B[cursor] == None:
  226.        raise IndexError, "delete from empty grabbag(?)"
  227.     # test to see if bag is empty (position cursor2 at nonempty slot)
  228.     cursor2 = cursor+1
  229.     if cursor2>=blen: cursor2 = START
  230.     while B[cursor2]==None:
  231.        cursor2 = cursor2+1
  232.        if cursor2>=blen: cursor2 = START
  233.        # since B[cursor] not yet deleted while will terminate
  234.     # get and delete the elt
  235.     (result,) = B[cursor]
  236.     B[cursor] = None
  237.     # cursor == cursor2 iff bag is empty
  238.     B[OLD] = cursor2
  239.     if B[NEW] == cursor2: B[NEW] = cursor
  240.     return result
  241.  
  242. def BGtest(n):
  243.     B = NewBG()
  244.     rn = range(n)
  245.     rn2 = range(n-2)
  246.     for i in rn:
  247.         for j in rn:
  248.             B = BGadd( (i,j), B)
  249.             B = BGadd( (j,i), B)
  250.             x = BGgetdel(B)
  251.         for j in rn2:
  252.             y = BGgetdel(B)
  253.         print (i, x, y)
  254.     return B
  255.